The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs typically require matching packets on a subset of fields of the packet header or flow label, with the semantics of a sequential search through the ACL rules. Access control and quality of service features are typically implemented based on programming contained in one or more ACLs. To implement features in hardware, one or more ACL lists are converted to associative memory entries which are programmed into an associative memory for performing matching operations to identify a desired result (e.g., drop, route, etc.) for a packet.
Associative memories are often used in a communications device for implementing the policies specified in ACLs and for identifying routing information. FIG. 1A shows one prior art associative memory 100 having multiple associative memory entries 102. Programming and lookup signals 101 are used to program associative memory entries 102, as well as to provide a lookup value for comparing to the associative memory entries 102 to generate entries' match results 119. Typically, but not always, a priority encoder 120 is included in or with an associative memory to identify a highest priority result 121 from entries' match results 119 which indicate a match was found for a given lookup value. In one embodiment associative memory entries may include binary content-addressable memory entries (e.g., include a value to be compared against), ternary content-addressable memory entries (e.g., include a value and mask used to identify a value to be compared against), or another type of associative memory entries.
FIG. 1B illustrates another prior art associative memory 110, which includes multiple search blocks 112, 114 and 116, each of which typically includes a block mask capability to be used to mask each entry (e.g., binary or ternary content-addressable memory entry) within its corresponding block in identifying a value to be compared against the provided lookup value.
FIG. 1C illustrates a typical prior art associative memory entry with comparison logic 140. A value to be compared 142, which typically includes a stored comparison value and possibly a mask (such as in a ternary content-addressable memory), and possibly this result are masked with a block mask. A comparison is made between the lookup value 145 and the value to be compared 142 to identify an entry match result 147 identifying whether there was a match (i.e., a hit) or there was not a match (e.g., a miss). FIG. 1D illustrates part of a typical prior art associative memory entry cell 160. The results of the bit-by-bit comparisons 161-169 are generated based on the lookup value and the value to be compared. A result line 171 is typically used to perform a wired-AND operation. If any one of the bit-by-bit comparison results 161-169 results in a miss (e.g., a low value), the corresponding bit match transistor 174 is turned on and the result line 171 becomes high due to Vcc 180, which produces a miss indication on result signal 185 (which in one embodiment is inverted by inverter 182 to drive the hit/miss indication signal 185); otherwise, a hit indication is produced on result signal 185.
A known prior binary content-addressable memory includes one bit per cell of each entry to identify the value of the cell used in matching. A known prior ternary content-addressable memory includes two bits per cell of each entry to identify the value of the cell used in matching, with these values being a one, a zero, or a wildcard case (i.e., matches both a zero and a one). In addition, known binary and ternary content-addressable memories may include an additional enable bit per entry to identify whether or not the entry should be matched against a lookup word. Also, known binary and ternary content-addressable memories may include additional enable bit(s) to identify whether or not portions (e.g., one or more cells) should be considered in identifying a match. In the case where an enable bit is used for each cell of an entry, then the number of enable bits for each entry will be at least the number of cells per entry, which may consume a substantial amount of space in a content-addressable memory, as well as consume additional resources to program and to error protect and/or correct these additional large number of enable bits.